package com.example.rwq_test.niuke.tree;

/**
 * 判断是否是二叉查找树
 *
 * @author renweiqiang
 * @version 1.0.0
 * @createTime 2023/11/10
 */
public class BinarySearchTree {
    public boolean isValidBST1 (TreeNode root) {
        // write code here
        return isValidBST(root, null, true);
    }

    public boolean isValidBST (TreeNode root, TreeNode parent, boolean flag) {
        if (root == null) {
            return true;
        }
        if (root.left != null && root.left.val >= root.val) {
            return false;
        }
        if (parent != null && flag && root.right != null && root.right.val >= parent.val) {
            return false;
        }
        if (root.right != null && root.right.val <= root.val) {
            return false;
        }
        if (parent != null && !flag && root.left != null && root.left.val <= parent.val) {
            return false;
        }
        return isValidBST(root.left, root, true) && isValidBST(root.right, root, false);
    }

    int pre = Integer.MIN_VALUE;
    public boolean isValidBST (TreeNode root) {
        // write code here
        if (root == null) {
            return true;
        }
        //先进入左子树
        if(!isValidBST(root.left)) {
            return false;
        }
        if(root.val < pre) {
            return false;
        }
        //更新最值
        pre = root.val;
        //再进入右子树
        return isValidBST(root.right);
    }
}
